# 152. 乘积最大子数组
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = nums[0]

        @cache
        def dfs(j, curMulti):
            if j < 0:
                return
            curMulti *= nums[j]
            nonlocal ans
            ans = max(curMulti, ans)
            dfs(j - 1, curMulti)

        for i in range(0, len(nums)):
            dfs(i, 1)
        return ans
